package simple.tree;

import struct.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/leaf-similar-trees/">872. 叶子相似的树</a>
 * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
 * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
 * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
 * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 * 示例 1：
 *   输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
 *   输出：true
 * 示例 2：
 *   输入：root1 = [1,2,3], root2 = [1,3,2]
 *   输出：false
 * 提示：
 *   给定的两棵树结点数在 [1, 200] 范围内
 *   给定的两棵树上的值在 [0, 200] 范围内
 * @author 刘学松
 * @date 2023-06-29 10:22
 */
public class 叶子相似的树 {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        if (list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (!list1.get(i).equals(list2.get(i))) {
                return false;
            }
        }
        return true;
    }

    public void dfs(TreeNode node, List<Integer> list) {
        if (node != null) {
            if (node.left == null && node.right == null) {
                list.add(node.val);
            } else {
                if (node.left != null) {
                    dfs(node.left, list);
                }
                if (node.right != null) {
                    dfs(node.right, list);
                }
            }
        }
    }
}
